1. Field of the Invention
The present invention relates to the design of lookup structures within computer systems. More specifically, the present invention relates to a method and apparatus for implementing a lock-free skip list that supports concurrent accesses within a computer system.
2. Related Art
A skip list is a dynamically sized sorted linked list that offers logarithmic time performance for searching, inserting, and deleting elements. William Pugh developed a basic design for a skip list to be used by a single thread (see “A Skip List Cookbook,” by William Pugh, University of Maryland Institute for Advanced Computer Studies UMIACS Technical Report No. UMIACS-TR-89-72.1).
A skip list is neither a single list (which takes linear search time), nor a tree (which requires re-balancing whenever it grows lop-sided in order to avoid requiring linear search time), but instead has an indexing scheme that is incorporated into its basic list structure.
Nodes in a skip list are mostly just normal linked-list nodes, but a procedure using random numbers chooses to make some of the new additions taller than the baseline—these serve to index into the list with search time proportional to the logarithm of the size of the list. Adjusting the distribution of random numbers selects the base of the logarithm—using more “tall” nodes reduces search time at the expense of the extra space; using shorter average heights is more compact but yields slower searches.
The head of the skip list is a special sentinel node representing negative infinity and carrying a set of pointers that are as “high” as the tallest node can be. The tail of the skip list is logically a terminator sentinel of similar height representing positive infinity, though it may be simulated by null pointers. The head pointers and all other pointers in the skip list point “forward” to the next node that reaches the “height” of that pointer. The top pointers may be missing, but once there is a node as tall as a given height, all those pointers “shorter” than it will be filled in.
Locating a given node (or where a future one will be inserted) is done by following the tallest pointer chain keeping track of a predecessor and successor nodes until the successor node has a value higher than the target node. This process loops by descending to the next lower layer and following the predecessor links at that level until the bottom layer is reached.
Subsequent to his description of the canonical skip list, Pugh also developed a technique based on locks to use skip lists in a multi-threaded environment (see “Concurrent Maintenance of Skip Lists,” by William Pugh, University of Maryland Technical Report No. CS-TR-2222.1 1989). However, when large numbers of processes access a skip list concurrently, contention for locks can become a serious impediment to system performance.
Hence, what is needed is a method and an apparatus for accessing a skip list in a multi-threaded environment without the performance problems associated with locks.